package txmusic;

public class FillArray {

    private long res = 0;

    public static void main(String[] args) {

        FillArray fillArray = new FillArray();
        System.out.println(fillArray.FillArray(new int[]{0,0,0,0,0,67,0,0}, 100));
    }

    public int FillArray (int[] a, int k) {
        // write code here
        int len = a.length;
        long ans = 1;
        for (int i = 0; i < len; i++){
            if (a[i] != 0){
                continue;
            } else {
                int beginIndex = i;
                int endIndex = i;
                int zeroNum = 1;
                i++;
                while (i < len && a[i] == 0){
                    zeroNum++;
                    endIndex = i;
                    i++;
                }
                res = 0;
                dfs((beginIndex - 1 >= 0 ? a[beginIndex - 1] : 1), (endIndex + 1 < len ? a[endIndex + 1] : k) , zeroNum);
                ans *= res;
            }
        }
        return (int) (ans%(1000000007));
    }

    public void dfs(int beginIndex, int endIndex, int zeroNum){
        if (zeroNum == 0){
            res++;
            return;
        }
        for (int i = beginIndex; i <= endIndex; i++){
            if (endIndex - i >= zeroNum - 2){
                dfs(i, endIndex, zeroNum - 1);
            }
        }
    }
}
